
package pkg11503;

/**
 *
 * @author xerxes
 */
import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;

public class Main {

    /**
     * @param args the command line arguments
     */
    int inf = (int) 1e5;
    BufferedReader reader;
    StringTokenizer token;
    HashMap< String, Integer > map =  new HashMap<String, Integer>();
    int[] root = new int [inf+10];
    int[] rank = new int [inf+10];
    int[] people = new int [inf+10];
    int F; //number of friendship
    public static void main(String[] args)throws IOException {
        Main ob = new Main();
        ob.run();
        System.exit(0);
    }
    public void run()throws IOException{
       // reader = new BufferedReader( new FileReader("in") );
        reader = new BufferedReader( new InputStreamReader(System.in) );
        token = new StringTokenizer("");
        int cases = nextInt();
        for( ; cases>0 ;--cases){
            
            doRest();
        }
        
    }
    public void doRest()throws IOException{
            Set();
            F = nextInt();
            int i;
            map.clear();
            int j=0;
            for(i=0;i<F;++i){
                String a = nextToken();
                String b = nextToken();
                int indx1,indx2;
                if(map.containsKey(a)){
                    indx1 = map.get(a);
                }
                else{
                    indx1 = ++j;
                    map.put(a, indx1);
                }
                if(map.containsKey(b)){
                    indx2 = map.get(b);
                }
                else{
                    indx2 = ++j;
                    map.put(b, indx2);
                } 
                Union( indx1, indx2 );
                System.out.println( people[ Find(indx1) ] );
            }
    }
    public void Set(){
        int i;
        for(i=0;i<inf;++i){
            root[i]=i;
            rank[i]=0;
            people[i]=1;
        }
    }
    public int Find(int x){
        if(x!=root[x]){
            root[x] = Find( root[x] );
        }
        return root[x];
    }
    public void Union(int x, int y){
        int rx = Find(x);
        int ry = Find(y);
        if(rx==ry)return ;
        if( rank[rx]>rank[ry] ){
            root[ry]=rx;
            people[ rx ]+= people[ry];
        }
        else{
            root[rx]=ry;
            people[ry]+=people[rx];
        }
        if( rank[rx]==rank[ry] ){
            rank[ry]+=1;
        }
    }
    int nextInt()throws IOException{
        return Integer.parseInt( nextToken() );
    }
    String nextToken()throws IOException{
        while( token==null || !token.hasMoreTokens() ){
            String line = reader.readLine();
            token = new StringTokenizer( line );
        }
        return token.nextToken();
    }
}
